package first.niuke.midding;

import java.util.Arrays;

/**
 * @ClassName NC91
 * @description:
 * @author: 荣燊
 * @create: 2021-06-26 13:29
 **/
public class NC91 {
    // 最长递增子序列
    public static void main(String[] args) {
        //输入：[2,1,5,3,6,4,8,9,7]，返回：[1,3,4,8,9]

    }

    // 最长递增子序列
    // 给定数组arr，设长度为n，输出arr的最长递增子序列。
    // （如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
    public int[] LIS (int[] arr) {
        // write code here

        return new int[0];
    }

    // 下面的两个方法都是返回最长递增子序列的长度

    // 解法一：动态规划，返回的是最长递增子序列的长度，时间复杂度是O(N^2)
    // dp[i]表示以num[i]结尾的数组的最长长度
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);

        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    // 解法二：动态规划+二分法
    // tail[k]代表 长度为 k+1k+1 子序列 的尾部元素值。
    public int lengthOfLIS1(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for (int num : nums) {
            int i = 0;
            int j = res;  // 表示tails数组中的拥有元素的个数，tails数组中元素严格递增的
            // 找出tails数组中，第一个比num值大的
            while (i < j) {
                int mid = (i+j) / 2;
                if (tails[mid] < num) {
                    i = mid + 1;
                } else {
                    j = mid;
                }
            }
            tails[i] = num;
            if (res == j) {
                res++;
            }
        }
        return res;
    }

}
